#include <iostream>

void mergearray(int* array,int* arrtmp,int low,int high){
    int k=low;//arrtmp数组下标
    int mid=(high+low)/2;
    int j=mid+1,i=low;
    while(i<=mid&&j<=high){
       if(array[i]<array[j]){
           arrtmp[k++]=array[i++];
       }else{
           arrtmp[k++]=array[j++];
       }
    }
    while(i<=mid){
        arrtmp[k++]=array[i++];
    }
    while(j<=high){
        arrtmp[k++]=array[j++];
    }
    while(low<=high){//把排好序的放回array
        array[low]=arrtmp[low];
        low++;
    }
}
void mergearray1(int* array,int low,int high){
    int *arrtmp=new int[high-low+1];
    int k=0;//arrtmp数组下标
    int mid=(high+low)/2;
    int j=mid+1,i=low;
    while(i<=mid&&j<=high){
        if(array[i]<=array[j]){
            arrtmp[k++]=array[i++];
        }else{
            arrtmp[k++]=array[j++];
        }
    }
    while(i<=mid){
        arrtmp[k++]=array[i++];
    }
    while(j<=high){
        arrtmp[k++]=array[j++];
    }
    for(i=low,k=0;i<=high;k++,i++){
        array[i]=arrtmp[k];
    }
    delete[] arrtmp;
}
void mergearray2(int* array,int low,int mid,int high){
    int *arrtmp=new int[high-low+1];
    int k=0;//arrtmp数组下标
    int j=mid+1,i=low;
    while(i<=mid&&j<=high){
        if(array[i]<=array[j]){
            arrtmp[k++]=array[i++];
        }else{
            arrtmp[k++]=array[j++];
        }
    }
    while(i<=mid){
        arrtmp[k++]=array[i++];
    }
    while(j<=high){
        arrtmp[k++]=array[j++];
    }
    for(k=0;low<=high;){
        array[low++]=arrtmp[k++];
    }
    delete[] arrtmp;
}
void mergeSort(int* array,int* arrtmp,int low,int high){
    if(low>=high) return;
    int mid =(high+low)/2;
    mergeSort(array,arrtmp,low,mid);
    mergeSort(array,arrtmp,mid+1,high);
    mergearray(array,arrtmp,low,high);
}
void mergeSort1(int* array,int low,int high){
    if(low>=high) return;
    int mid =(high+low)/2;
    mergeSort1(array,low,mid);
    mergeSort1(array,mid+1,high);
    mergearray1(array,low,high);
}
void mergeSort2(int* array,int low,int high){
    if(low<high){
    int mid =(high+low)/2;
    mergeSort2(array,low,mid);
    mergeSort2(array,mid+1,high);
    mergearray2(array,low,mid,high);
    }
}
int main() {
    std::cout << "Hello, World!" << std::endl;
    int array[]={1,7,8,4,3,2,8,5};
    int brray[8];
    mergeSort1(array,0, 7);
    for(int i=0;i<=(sizeof(array)/sizeof(int)-1);i++){
        std::cout<<array[i]<<"\t";
    }
    std::cout<<std::endl;
    return 0;
}
